package com.dmall.play.interview.chapter09;

import java.util.ArrayList;
import java.util.List;

/**
 * 记忆化搜索
 */
public class Leetcode120V3 {

    Integer[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return  dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> item1 = new ArrayList<>();
        item1.add(2);
        List<Integer> item2 = new ArrayList<>();
        item2.add(3);
        item2.add(4);
        List<Integer> item3 = new ArrayList<>();
        item3.add(6);
        item3.add(5);
        item3.add(7);
        List<Integer> item4 = new ArrayList<>();
        item4.add(4);
        item4.add(1);
        item4.add(8);
        item4.add(3);
        triangle.add(item1);
        triangle.add(item2);
        triangle.add(item3);
        triangle.add(item4);

        Leetcode120V3 leetcode120 = new Leetcode120V3();
        System.out.println(leetcode120.minimumTotal(triangle));
    }
}
